package link_list;


import java.util.Iterator;

/**
 * @author swing
 * @description
 * @create 2022 - 11 - 18 22:48
 */
public class LinkedList_Double<T> implements Iterable<T> {

    private Node head; //:记录首结点

    private Node last; //:记录尾结点  方便从尾部开始查找

    private int N; //:记录链表的长度

    /**
     * 初始化头结点
     */
    public LinkedList_Double() {
        this.head = new Node(null, null, null);
        this.last = null;
        this.N = 0;
    }


    private class Node {
        public T item;
        public Node prev;
        public Node next;

        public Node(T item, Node prev, Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }


    }
    /*
    1.public void clear()：空置线性表
    2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false
    3.public int length():获取线性表中元素的个数
    4.public T get(int i):读取并返回线性表中的第i个元素的值
    5.public void insert(T t)：往线性表中添加一个元素；
    6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
    7.public T remove(int i):删除并返回线性表中第i个数据元素。
    8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
    9.public T getFirst():获取第一个元素
    10.public T getLast():获取最后一个元素
     */

    /**
     * 清空链表：
     * 1.头结点不指向下个节点
     * 2，长度为0
     * 3.尾结点为null
     */
    public void clear() {
        this.head.next = null;
        this.head.prev = null;  //可以不写
        this.head.item = null;  //可以不写  语义更明显
        this.N = 0;
        this.last = null;
    }

    public boolean isEmpty() {
        return this.N == 0;
    }

    public int length() {
        return N;
    }

    /**
     * 获取第一个节点
     *
     * @return
     */
    public T getFirst() {
        if (isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    /**
     * 获取最后一个节点
     *
     * @return
     */
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return last.item;
    }

    public void insert(T t) {
        //当链表为空时 直接插到头结点的后面
        if (isEmpty()) {
            Node node = new Node(t, head, null);
            last = node;
            //让头结点指向尾结点
            head.next = last;
        }//当头结点不为空时  插入到最后一个节点的后面
        else {
            //如果链表不为空  创建一个原最后一个节点很容易理解
            Node oldLast = last;

            Node lastnode = new Node(t, oldLast, null);
            //让原最后一个节点指向新的最后一个节点
            oldLast.next=lastnode;
            //让这个节点成为最后一个节点
            last=lastnode;

        }
        N++;
    }

    /**
     * 在第i个位置插入元素
     *
     * @param i
     * @param t
     */
    public void insert(int i, T t) {
        //找到第i个node的上个元素
        Node node = head;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        //第i个node
        Node curr = node.next;

        Node lastNode = new Node(t, node, curr);  //这里时从新节点指向上下两个节点
        node.next = lastNode;
        curr.prev = lastNode;
        N++;
    }

    /**
     * 获取链表第i个位置的值
     *
     * @param i
     * @return
     */
    public T get(int i) {
        Node node = head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    /**
     * 删除第i个节点
     * 第i个节点的上个节点指向第i个节点的下个节点
     * 第i个节点的下个节点指向第i个节点
     *
     * @param i
     * @return
     */
    public T remove(int i) {
        //第i个节点的上个节点
        Node node = head;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        Node curr = node.next;
        Node nextNode = curr.next;
        node.next = nextNode;
        nextNode.prev = node;
        N--;
        return curr.item;

    }

    /**
     * 返回第i个节点的位置
     *
     * @param t
     * @return
     */
    public int indexOf(T t) {
        Node node = head.next;
        for (int index = 0; node != null; index++) {
            if (node.equals(t)) {
                return index;
            }
        }
        return -1;
    }


    /**
     * 便利链表的
     *
     * @return
     */
    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }

    private class TIterator implements Iterator {
        private Node n;

        public TIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}
